package com.leetcode.partition15;

import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2022/2/3 14:15
 */
public class LC1414和为K的最少斐波那契数字数目 {

    private static List<Integer> fib = new ArrayList<>();

    static {
        //预处理出不超过1e9的斐波那契数列
        fib.add(1);
        fib.add(1);
        int t = 0;
        while (t <= 1e9) {
            int a = fib.get(fib.size() - 2), b = fib.get(fib.size() - 1);
            t = a + b;
            fib.add(t);
        }
    }

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int k = Integer.parseInt(reader.readLine());
        writer.write(findMinFibonacciNumbers(k) + "\n");
        writer.flush();
    }

    public static int findMinFibonacciNumbers(int k) {
        //每次从fib中查找小于等于k的最大的数
        int ans = 0;
        while (k != 0) {
            int left = 0, right = fib.size() - 1;
            while (left < right) {
                int mid = (left + right + 1) >>> 1;
                if (fib.get(mid) <= k) left = mid;
                else right = mid - 1;
            }
            k -= fib.get(left);
            ans++;
        }
        return ans;
    }
}
